Breaking RSA Public Key Encryption created with openssl¶
Source notebook: breaking asymetric certs jupyter interactive notebook
A small demonstration how to retrieve private key from public key by integer factorization.
We need to use the OpenSSL unsafe, because for demonstration we do not want seriously big keys.
The factorization is done by sympy, because it is a good science research tool.
Lets start with RSA keys creation with openssl.
%%bash
openssl-unsafe genrsa -out private_rsa_key.pem 128 2> /dev/null
openssl pkey -pubout -in private_rsa_key.pem -out public_rsa_key.pem 2> /dev/null
openssl rsa -in private_rsa_key.pem -check -noout
cat public_rsa_key.pem | wc -l
RSA key ok 3
Create some text, and encrypt it with public key.
%%bash
echo "sens" > unencrypted.txt
openssl pkeyutl -encrypt -pubin -inkey public_rsa_key.pem -in unencrypted.txt -out encrypted.txt
cat unencrypted.txt
echo
cat encrypted.txt | xxd -p
The history saving thread hit an unexpected error (OperationalError('database is locked')).History will not be written to the database.
sens
9b79d49113b10b0fc6bab059a91bdee4
Decrypt it with private key.
%%bash
openssl pkeyutl -decrypt -inkey private_rsa_key.pem -in encrypted.txt -out decrypted.txt
cat decrypted.txt
sens
Lets look at the private and public key.
%%bash
openssl pkey -in private_rsa_key.pem -text -noout
Private-Key: (128 bit, 2 primes)
modulus:
00:bf:5b:da:5c:a1:0e:77:de:41:05:8d:c9:6c:7b:
91:49
publicExponent: 65537 (0x10001)
privateExponent:
6c:1d:d5:8e:28:61:28:4f:ac:44:3b:81:a0:de:a2:
d1
prime1: 16710255007646193503 (0xe7e6c0650cf1975f)
prime2: 15221759033407103063 (0xd33e8d314ad2e057)
exponent1: 11183940604549872371 (0x9b3556b98b433af3)
exponent2: 13752933726675538911 (0xbedc3c5bb5fc13df)
coefficient: 14863620565872574889 (0xce463027610681a9)
%%bash
openssl pkey -pubin -in public_rsa_key.pem -text -noout
Public-Key: (128 bit)
Modulus:
00:bf:5b:da:5c:a1:0e:77:de:41:05:8d:c9:6c:7b:
91:49
Exponent: 65537 (0x10001)
%%bash
openssl pkey -pubin -in public_rsa_key.pem -noout -text | awk -F'[ ]' '/Exponent:/{print $2}' | tee pubExp
65537
%%bash
openssl rsa -pubin -in public_rsa_key.pem -modulus | awk -F'=' '{print $2}' | xargs -I '{}' echo "ibase=16; {}" | bc | tee modint
254359475113174726019480016394361999689
from sympy.ntheory import factorint
with open('modint', 'rb') as f:
mod = int(f.read())
print(mod)
254359475113174726019480016394361999689
primes = factorint(mod)
primes_list = list(primes.keys())
primes_list.sort(reverse=True) # order matters for pinv
[p,q] = primes_list
phi = (p - 1) * (q - 1)
with open('pubExp', 'rb') as f:
e = int(f.read())
d = pow(e, -1, phi)
dp = d % (p - 1)
dq = d % (q - 1)
pinv = pow(q, -1, p)
p,q, pinv, dp , dq, d
(16710255007646193503, 15221759033407103063, 14863620565872574889, 11183940604549872371, 13752933726675538911, 143711531569809935667896416240266027729)
with open('asn1_rsa', 'wb') as out_file:
text = (
"asn1=SEQUENCE:rsa_key\n\n[rsa_key]\n"
"version=INTEGER:0\n"
"modulus=INTEGER:"+str(mod)+"\n"
"pubExp=INTEGER:"+str(e)+"\n"
"privExp=INTEGER:"+str(d)+"\n"
"p=INTEGER:"+str(p)+"\n"
"q=INTEGER:"+str(q)+"\n"
"e1=INTEGER:"+str(dp)+"\n"
"e2=INTEGER:"+str(dq)+"\n"
"coeff=INTEGER:"+str(pinv)+"\n"
)
out_file.write(text.encode())
%%bash
openssl asn1parse -genconf asn1_rsa -out recreated.bin
openssl pkey -inform DER -outform PEM -in recreated.bin -out recreated2.pem
0:d=0 hl=2 l= 100 cons: SEQUENCE
2:d=1 hl=2 l= 1 prim: INTEGER :00
5:d=1 hl=2 l= 17 prim: INTEGER :BF5BDA5CA10E77DE41058DC96C7B9149
24:d=1 hl=2 l= 3 prim: INTEGER :010001
29:d=1 hl=2 l= 16 prim: INTEGER :6C1DD58E2861284FAC443B81A0DEA2D1
47:d=1 hl=2 l= 9 prim: INTEGER :E7E6C0650CF1975F
58:d=1 hl=2 l= 9 prim: INTEGER :D33E8D314AD2E057
69:d=1 hl=2 l= 9 prim: INTEGER :9B3556B98B433AF3
80:d=1 hl=2 l= 9 prim: INTEGER :BEDC3C5BB5FC13DF
91:d=1 hl=2 l= 9 prim: INTEGER :CE463027610681A9
Parameters are the same.
%%bash
openssl pkey -in private_rsa_key.pem -text -noout > a
openssl pkey -in recreated2.pem -text -noout > b
diff -s a b
Files a and b are identical
The PEM files are different.
%%bash
cat private_rsa_key.pem
echo " "
cat recreated2.pem
-----BEGIN RSA PRIVATE KEY----- MGQCAQACEQC/W9pcoQ533kEFjclse5FJAgMBAAECEGwd1Y4oYShPrEQ7gaDeotEC CQDn5sBlDPGXXwIJANM+jTFK0uBXAgkAmzVWuYtDOvMCCQC+3DxbtfwT3wIJAM5G MCdhBoGp -----END RSA PRIVATE KEY----- -----BEGIN PRIVATE KEY----- MHoCAQAwDQYJKoZIhvcNAQEBBQAEZjBkAgEAAhEAv1vaXKEOd95BBY3JbHuRSQID AQABAhBsHdWOKGEoT6xEO4Gg3qLRAgkA5+bAZQzxl18CCQDTPo0xStLgVwIJAJs1 VrmLQzrzAgkAvtw8W7X8E98CCQDORjAnYQaBqQ== -----END PRIVATE KEY-----
But they function the same way.
%%bash
openssl pkeyutl -decrypt -inkey private_rsa_key.pem -in encrypted.txt -out decrypted.txt
openssl pkeyutl -decrypt -inkey recreated2.pem -in encrypted.txt -out redecrypted2.txt
cat decrypted.txt
cat redecrypted2.txt
sens sens